1. Field of the Invention
The present invention relates to a variable length coding method, and more particularly, to a variable length coding method for reducing the number of bits generated by dynamically varying the mapping between symbols and bit patterns depending on the occurrence statistics of symbols of an input image. The present invention also relates to a variable length coding apparatus for performing the variable length coding method. The present invention also relates to a variable length decoding method for decoding a bit pattern which has been coded by the variable length coding method. The present invention also relates to a variable length decoding apparatus for performing the variable length decoding method. The present invention is based on Korean Application No. 99-31672 which is incorporated herein by reference.
2. Description of the Related Art
Standardized video CODECs adopt a variable length coding (VLC) technique to obtain high coding efficiency. FIG. 1 shows a block diagram of a conventional variable length coding apparatus. Referring to FIG. 1, a VLC unit 10 receives a symbol and performs variable length coding based on a VLC table 12. In the VLC table 12, each symbol is mapped onto a bit pattern of a different length based on average symbol statistics of usual test patterns.
However, the symbol statistics vary considerably depending on a video sequence and coding parameters. Accordingly, in a conventional variable length coding technology, it sometimes happens that a large number of bits is allocated to a symbol even if the symbol appears frequently. This causes a problem of decreasing the efficiency of compression of bits by variable length coding.
To solve this problem, a conventional method prepares a plurality of VLC tables and selectively uses one among the prepared VLC tables. However, this method is disadvantageous in that it is difficult to sort a sequence characteristic and in that the efficiency of bit compression may be decreased because the characteristics of occurrence probabilities of symbols vary with coding parameters even with respect to the same sequence.
To solve the above problem, an object of the present invention is to provide a variable length coding method capable of efficiently reducing a bit rate by taking into account the occurrence statistics of symbols in an input image.
Another object of the present invention is to provide a variable length coding apparatus for performing this method.
Yet another object of the present invention is to provide a variable length decoding method for decoding a bit pattern which has been coded by the variable length coding method.
A further object of the present invention is to provide a variable length decoding apparatus for performing the variable length decoding.
To achieve one of the above objects of the invention, there is provided a method of variable length coding input symbols to generate bit patterns. The method includes the steps of (a) analyzing the occurrence statistics of symbols with respect to previous frames, (b) resetting a mapping relationship based on the analyzed occurrence statistics of symbols, and (c) variable length coding a current frame based on the reset mapping relationship.
It is preferable that the step (a) includes the step of calculating the occurrence statistics Pi of an i-th symbol ai in N of symbols using W previous frames in accordance with       P    i    =                    ∑                  t          =                      n            -            1                                    n          -          W                    ⁢              xe2x80x83            ⁢                        c          i                ⁢                  xe2x80x83                ⁢                  (          t          )                                    ∑                  j          =          0                          N          -          1                    ⁢              xe2x80x83            ⁢                        ∑                      t            =                          n              -              1                                            n            -            W                          ⁢                  xe2x80x83                ⁢                              c            j                    ⁢                      xe2x80x83                    ⁢                      (            t            )                              
where i is a predetermined positive number indicating a symbol number, ci(t) is the number of occurrences of the symbol ai in a t-th frame, and W is a predetermined positive integer indicating the number of frames used for analyzing the occurrence statistics of symbols.
Preferably, the step (a) analyzes the occurrence statistics of symbols using only symbols that are obtained from a frame immediately before the current frame.
Alternatively, the step (a) may analyze the occurrence statistics of symbols using symbols that are obtained from all the previous frames.
It is preferable that the step (b) includes the steps of reordering the symbols ai based on the occurrence statistics Pi of the symbols ai, such that Pixe2x80x2xe2x89xa7Pixe2x80x2+1 if ixe2x80x2xe2x89xa6ixe2x80x2+1, where ixe2x80x2 is a new number of a symbol ai, and resetting the mapping relationship such that m(i)=ixe2x80x2 based on the reordered relationship.
The variable length coding method further includes the step (c-1) for detecting whether the scene of each of the previous frames is similar to the scene of the current frame before the step (c). The current frame is variable length coded using a default variable length coding table and the mapping relationship when it is determined that the scene of a previous frame is not similar to the scene of the current frame in the step (c-1). The step (c) is performed when it is determined that the scene of a previous frame is similar to the scene of the current frame in the step (c-1).
The step (c-1) preferably includes the steps of (d-1) checking to find whether the ratio of occurrences of an intra macroblock in a frame immediately before the current frame is equal to or greater than a predetermined threshold, and (d-2) determining that the scene is changed if the ratio of occurrences of an intra macroblock in a frame immediately before the current frame is equal to or greater than the predetermined threshold, and, if not, determining that the scene is not changed.
Alternatively, the step (c-1) may include the steps of (e-1) checking to find whether the difference between the number of bits, which are generated by performing the mapping between a symbol and a bit pattern in a current image frame according to the method described above, and the number of bits, which are generated by using a default variable length coding definition, is equal to or greater than a predetermined number of bits; and (e-2) determining that the scene is changed if the difference is equal to or greater than the predetermined number of bits in the step (e-1) and, if not, determining that the scene is not changed.
Alternatively, the step (c-1) may include the steps of (f-1) measuring the sum of absolute difference (SAD) between a current image frame and a motion compensated image frame; and (f-2) determining that the scene is changed if the SAD is equal to or greater than a predetermined value in the step (f-1), and, otherwise, determining that the scene is not changed.
To achieve one of the above objects of the invention, there is provided an apparatus of variable length coding input symbols to generate bit patterns. The apparatus includes a statistical analyzer for analyzing the occurrence statistics of the input symbols with respect to previous frames, a mapping relationship resetter for resetting a mapping relationship based on the analyzed occurrence statistics of the symbols, and a variable length coding unit for variable length coding a current frame based on the reset mapping relationship.
To achieve one of the above objects of the invention, there is provided a digital image coding method to which variable length coding for generating bit patterns by variable length coding input symbols is applied. The method includes the steps of (a) analyzing the occurrence statistics of symbols with respect to previous frames, (b) resetting a mapping relationship based on the analyzed occurrence statistics of symbols, and (c) variable length coding a current frame based on the reset mapping relationship.
To achieve one of the above objects of the invention, there is provided a method of variable length decoding input bit patterns which have been variable length coded. The method includes the steps of (a) variable length decoding the input bit patterns using a default variable length coding table to obtain decoded symbols, (b) analyzing the occurrence statistics of the decoded symbols with respect to previous frames of a current frame, (c) resetting a mapping relationship based on the analyzed occurrence statistics of the input symbols, and (d) replacing the decoded symbols with symbols corresponding to the reset mapping relationship in the current frame.
To achieve one of the above objects of the invention, there is provided an apparatus for variable length decoding input bit patterns which have been variable length coded. The apparatus includes a variable length decoder for variable length decoding the input bit patterns using a default variable length coding table to obtain decoded symbols, a statistical analyzer for analyzing the occurrence statistics of the decoded symbols with respect to previous frames of a current frame, a mapping relationship resetter for resetting a mapping relationship between symbols and bit patterns based on the analyzed occurrence statistics of the input symbols, and a symbol replacer for replacing the decoded symbols with symbols corresponding to the reset mapping relationship in the current frame.
To achieve one of the above objects of the invention, there is provided a digital image decoding apparatus using variable length decoding. The apparatus includes a variable length decoding unit including a variable length decoder for variable length decoding the input bit patterns using a default variable length coding table to obtain decoded symbols, a statistical analyzer for analyzing the occurrence statistics of the decoded symbols with respect to previous frames of a current frame, a mapping relationship resetter for resetting a mapping relationship between symbols and bit patterns based on the analyzed occurrence statistics of the input symbols, and a symbol replacer for replacing the decoded symbols with symbols corresponding to the reset mapping relationship in the current frame.